Jump to content

Gordan's lemma

From Wikipedia, the free encyclopedia

Gordan's lemma is a lemma in convex geometry and algebraic geometry. It can be stated in several ways.

  • Let be a matrix of integers. Let be the set of non-negative integer solutions of . Then there exists a finite subset of vectors in , such that every element of is a linear combination of these vectors with non-negative integer coefficients.[1]
  • The semigroup of integral points in a rational convex polyhedral cone is finitely generated.[2]
  • An affine toric variety is an algebraic variety (this follows from the fact that the prime spectrum of the semigroup algebra of such a semigroup is, by definition, an affine toric variety).

The lemma is named after the mathematician Paul Gordan (1837–1912). Some authors have misspelled it as "Gordon's lemma".

Proofs

[edit]

There are topological and algebraic proofs.

Topological proof

[edit]

Let be the dual cone of the given rational polyhedral cone. Let be integral vectors so that Then the 's generate the dual cone ; indeed, writing C for the cone generated by 's, we have: , which must be the equality. Now, if x is in the semigroup

then it can be written as

where are nonnegative integers and . But since x and the first sum on the right-hand side are integral, the second sum is a lattice point in a bounded region, and so there are only finitely many possibilities for the second sum (the topological reason). Hence, is finitely generated.

Algebraic proof

[edit]

The proof[3] is based on a fact that a semigroup S is finitely generated if and only if its semigroup algebra is a finitely generated algebra over . To prove Gordan's lemma, by induction (cf. the proof above), it is enough to prove the following statement: for any unital subsemigroup S of ,

If S is finitely generated, then , v an integral vector, is finitely generated.

Put , which has a basis . It has -grading given by

.

By assumption, A is finitely generated and thus is Noetherian. It follows from the algebraic lemma below that is a finitely generated algebra over . Now, the semigroup is the image of S under a linear projection, thus finitely generated and so is finitely generated. Hence, is finitely generated then.

Lemma: Let A be a -graded ring. If A is a Noetherian ring, then is a finitely generated -algebra.

Proof: Let I be the ideal of A generated by all homogeneous elements of A of positive degree. Since A is Noetherian, I is actually generated by finitely many , homogeneous of positive degree. If f is homogeneous of positive degree, then we can write with homogeneous. If f has sufficiently large degree, then each has degree positive and strictly less than that of f. Also, each degree piece is a finitely generated -module. (Proof: Let be an increasing chain of finitely generated submodules of with union . Then the chain of the ideals stabilizes in finite steps; so does the chain ) Thus, by induction on degree, we see is a finitely generated -algebra.

Applications

[edit]

A multi-hypergraph over a certain set is a multiset of subsets of (it is called "multi-hypergraph" since each hyperedge may appear more than once). A multi-hypergraph is called regular if all vertices have the same degree. It is called decomposable if it has a proper nonempty subset that is regular too. For any integer n, let be the maximum degree of an indecomposable multi-hypergraph on n vertices. Gordan's lemma implies that is finite.[1] Proof: for each subset S of vertices, define a variable xS (a non-negative integer). Define another variable d (a non-negative integer). Consider the following set of n equations (one equation per vertex):Every solution (x,d) denotes a regular multi-hypergraphs on , where x defines the hyperedges and d is the degree. By Gordan's lemma, the set of solutions is generated by a finite set of solutions, i.e., there is a finite set of multi-hypergraphs, such that each regular multi-hypergraph is a linear combination of some elements of . Every non-decomposable multi-hypergraph must be in (since by definition, it cannot be generated by other multi-hypergraph). Hence, the set of non-decomposable multi-hypergraphs is finite.

See also

[edit]
  • Birkhoff algorithm is an algorithm that, given a bistochastic matrix (a matrix which solves a particular set of equations), finds a decomposition of it into integral matrices. It is related to Gordan's lemma in that it shows that the set of these matrices is generated by a finite set of integral matrices.

References

[edit]
  1. ^ a b Alon, N; Berman, K.A (1986-09-01). "Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory". Journal of Combinatorial Theory, Series A. 43 (1): 91–97. doi:10.1016/0097-3165(86)90026-9. ISSN 0097-3165.
  2. ^ David A. Cox, Lectures on toric varieties. Lecture 1. Proposition 1.11.
  3. ^ Bruns, Winfried; Gubeladze, Joseph (2009). Polytopes, rings, and K-theory. Springer Monographs in Mathematics. Springer. doi:10.1007/b105283. ISBN 978-0-387-76355-2., Lemma 4.12.

See also

[edit]